Homomorphic encryption (HE) is a type of encryption that permits various operations to be performed on encrypted data. A characteristic of homomorphic is that the output of the mathematical functions on the encrypted data, after being decrypted, matches the output of mathematical function performed on the underlying unencrypted data.
Homomorphic encryption enables performing arithmetic operations on encrypted data without knowledge of any secret decryption key. Most HE schemes to date have followed Gentry's or similar encryption schemes, but these schemes, that can generally evaluate low-depth circuits, remain inefficient due to required bootstrapping.
A fully homomorphic encryption scheme generally allows the computation of arbitrary functions over encrypted data without requiring the use of a decryption key. Homomorphic encryption is desired in a wide variety of fields that use cryptology. However, one drawback, is that homomorphic encryption and decryption algorithms tend to be processor-intensive and inefficient.
The most widely known existing solution to the fully homomorphic encryption problem is attributable to Craig Gentry with relevant software currently under development by IBM. This solution relies in its security on variants of the bounded-distance decoding problem that has the property of random self-reducibility. While this property has been shown to provide good evidence of security, the resulting homomorphic encryption algorithm is too inefficient to be practical in its application.
Accordingly, this solution is too inefficient to be practical. As a point of comparison and to further illustrate the point, Gentry's algorithm takes about 1800 seconds to encrypt a database with 106 entries, whereas the disclosed algorithm takes about 5 seconds (non-optimized). The disclosed algorithm is useful for doing private searches on an encrypted database as well as private information retrieval.
By way of background, ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher to decrypt it. Ciphertex is the result of encryption performed on plaintext using an algorithm, called a cipher. A homomorphism is a structure preserving map between two algebraic structures (such as groups, rings or vector spaces) and is used in enabling computations on encrypted data. Homomorphic encryption is a form of encryption that allows computations to be carried out on ciphertext, thus generating an encrypted result which, when decrypted, matches the result of operations performed on the plaintext.
Homomorphic encryption is considered a desirable feature in modern communication system architectures. Homomorphic encryption permits the chaining together of different services without exposing the data to each of those services. A cryptosystem that supports arbitrary computation on ciphertexts is known as fully homomorphic encryption (FHE) and is considered more powerful than homomorphic encryption. Such a scheme enables the construction of programs for any desirable functionality, which can be run on encrypted inputs to produce an encryption of the result. Since such a program need never decrypt its inputs, it can be run by an untrusted party without revealing its inputs and internal state. Therefore, the existence of an efficient and fully homomorphic cryptosystem would have great practical implications in the outsourcing of private computations, for instance, in the context of cloud computing.
In order to provide semantic security, encryption has to be randomized but, on the other hand, a homomorphism should map zero to zero. In order to resolve this conflict, the ciphertext zero is “masked” by “noise”. However, during any computation on encrypted data, this “noise” tends to accumulate and has to be occasionally reduced by recryption (a process also known as “bootstrapping”) that produces the equivalent ciphertext but, with less noise. Even further, recryption is an expensive procedure and in effect, limits real-life applications of existing FHE solutions such as the solution proposed by Gentry.
There were other proposed solutions for fully homomorphic encryption following Gentry's such as methods disclosed by Z. Brakerski and V. Vaikuntanathan, Efficient fully homomorphic encryption from (standard) LWE, In: FOCS 2011, 97-106, IEEE Computer Soc., Los Alamitos, Calif., 2011; M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan, Fully homomorphic encryption over the integers, In: Advances in Cryptology—EUROCRYPT 2010, Lecture Notes Comput. Sci. 6110 (2010), 24-43; or L. Ducas and D. Micciancio, FHE Bootstrapping in less than a second, preprint, http://eprint.iacr.org/2014/816. However, each of these methods generally implement bootstrapping techniques and thus, are also considered inefficient for similar reasons described in connection with Gentry's proposed solution.
An improved homomorphic encryption algorithm with increased efficiency on computation of encrypted data is therefore desired.
It is further desirable to implement a new practical private-key fully homomorphic encryption scheme based on homomorphisms between rings. Such FHE scheme would be implemented in conducting private search and private information retrieval on an encrypted database as well as for delegating computations on private data to a remote server, such as a cloud.
It is further desirable to implement a system and method using an FHE scheme that is unconditionally (i.e., without any computational assumptions) secure against ciphertext-only attack.
It is further desirable to provide a system and method with practical instantiation of an FHE scheme whereby resultant computation on encrypted data is accomplished without accumulating noise and is in orders of magnitude more efficient than currently available implementations.
It is yet further desirable to provide a system and method that implements unconditional ciphertext security for encryption of nonzero elements, even if the public is able to recognize encryptions of zero (0). This system and method achieves a very efficient private search on encrypted database without sacrificing any privacy of the data.
It is yet further desirable to provide a system and method that is private-key. Such a FHE private-key environment provides flexibility in terms of how much information the data owner is willing to give to the entity that stores (and operates on) any such encrypted data. In particular, this can provide a customer (including a company that holds sensitive data) with a “toolbox” for building their own instantiation of a general FHE scheme, so that any third party systems outside of the company would not have access to details of the encryption/decryption mechanisms, even though the public may be able to access and operate on encrypted data. This system and method would render “security through obscurity” impossible for FHE schemes, so while there should be some minimum amount of information available to the public, this minimum is essentially just the general framework.